Aleksandrov từng sáng tác bài ái quốc ca "Muôn năm Tổ quốc chúng ta" (Да здравствует наша держава) (sau được phổ lời), nhờ những ấn tượng về chiến thắng của quân đội Xô viết trước cửa ngõ Moskva năm 1941, để tham dự cuộc thi sáng tác Quốc ca Liên Xô. Tuy nhiên, nó đã bị từ chối.[5][6][7] Mặc dù vậy, bài hát (được thay đổi lời) đã trở thành quốc ca Cộng hòa Moldova Transnistria vào thập niên 1990.[7][8] Nó thường được sử dụng trong các cuộc duyệt binh tại Liên Xô và ngày nay là Nga.[9] Ngoài ra, bài hát còn được chuyển thể như một hành khúc quân đội.